{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Copy List with Random Pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: copyRandomList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #随机链表的复制"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的链表，每个节点包含一个额外增加的随机指针 <code>random</code> ，该指针可以指向链表中的任何节点或空节点。</p>\n",
    "\n",
    "<p>构造这个链表的&nbsp;<strong><a href=\"https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin\" target=\"_blank\">深拷贝</a></strong>。&nbsp;深拷贝应该正好由 <code>n</code> 个 <strong>全新</strong> 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 <code>next</code> 指针和 <code>random</code> 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。<strong>复制链表中的指针都不应指向原链表中的节点 </strong>。</p>\n",
    "\n",
    "<p>例如，如果原链表中有 <code>X</code> 和 <code>Y</code> 两个节点，其中 <code>X.random --&gt; Y</code> 。那么在复制链表中对应的两个节点 <code>x</code> 和 <code>y</code> ，同样有 <code>x.random --&gt; y</code> 。</p>\n",
    "\n",
    "<p>返回复制链表的头节点。</p>\n",
    "\n",
    "<p>用一个由&nbsp;<code>n</code>&nbsp;个节点组成的链表来表示输入/输出中的链表。每个节点用一个&nbsp;<code>[val, random_index]</code>&nbsp;表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>val</code>：一个表示&nbsp;<code>Node.val</code>&nbsp;的整数。</li>\n",
    "\t<li><code>random_index</code>：随机指针指向的节点索引（范围从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n-1</code>）；如果不指向任何节点，则为&nbsp;&nbsp;<code>null</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你的代码 <strong>只</strong> 接受原链表的头节点 <code>head</code> 作为传入参数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png\" style=\"height: 142px; width: 700px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [[7,null],[13,0],[11,4],[10,2],[1,0]]\n",
    "<strong>输出：</strong>[[7,null],[13,0],[11,4],[10,2],[1,0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png\" style=\"height: 114px; width: 700px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [[1,1],[2,1]]\n",
    "<strong>输出：</strong>[[1,1],[2,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png\" style=\"height: 122px; width: 700px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [[3,null],[3,0],[3,null]]\n",
    "<strong>输出：</strong>[[3,null],[3,0],[3,null]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 1000</code><meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>Node.random</code>&nbsp;为&nbsp;<code>null</code> 或指向链表中的节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [copy-list-with-random-pointer](https://leetcode.cn/problems/copy-list-with-random-pointer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [copy-list-with-random-pointer](https://leetcode.cn/problems/copy-list-with-random-pointer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[7,null],[13,0],[11,4],[10,2],[1,0]]', '[[1,1],[2,1]]', '[[3,null],[3,0],[3,null]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, next, random):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return \n",
    "        \n",
    "        head2 = Node(head.val,None,head.random)\n",
    "        p1 = head.next\n",
    "        p2 = head2\n",
    "        node_map = {None:None, head:head2}\n",
    "        while p1:\n",
    "            new_node = Node(p1.val,None,p1.random)\n",
    "            node_map[p1] = new_node\n",
    "            p2.next = new_node\n",
    "            p1=p1.next\n",
    "            p2=p2.next\n",
    "            \n",
    "        p2 = head2\n",
    "        while p2:\n",
    "            p2.random = node_map[p2.random]\n",
    "            p2=p2.next\n",
    "        return head2\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, next, random):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head == None:\n",
    "            return None\n",
    "        \n",
    "        p = head\n",
    "        while(p!=None):\n",
    "            cur = Node(p.val,None,None)\n",
    "            tmp = p.next\n",
    "            p.next = cur\n",
    "            cur.next = tmp\n",
    "            p = tmp\n",
    "        \n",
    "        p = head \n",
    "        while(p!=None):\n",
    "            if p.random != None:\n",
    "                p.next.random = p.random.next\n",
    "            p = p.next.next\n",
    "        \n",
    "        p = head\n",
    "        dummy = Node(-1,None,None)\n",
    "        cur = dummy\n",
    "        while p != None:\n",
    "            tmp = p.next.next\n",
    "            \n",
    "            copy = p.next\n",
    "            cur.next = copy\n",
    "            cur = copy\n",
    "            \n",
    "            p.next = tmp\n",
    "            p = tmp\n",
    "        \n",
    "        return dummy.next\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        \"\"\"\n",
    "        直观的方案是先复制next，然后复制random，但是每次需要遍历才知道random指向哪个，因此复杂度为O(n^2)\n",
    "        这里采用三步走：\n",
    "        1. 复制next\n",
    "        2. 复制random\n",
    "        3. 断开新老链表\n",
    "        \"\"\"\n",
    "        h = self.cloneNodes(head)\n",
    "        h = self.setNodes(h)\n",
    "        res = self.reconNodes(h)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def cloneNodes(self, head):\n",
    "        # p_head指向原先链表的每个节点\n",
    "        p_head = head\n",
    "        while p_head:\n",
    "            tmp = Node(p_head.val, p_head.next, p_head.random)\n",
    "            p_head.next = tmp\n",
    "            p_head = tmp.next\n",
    "        return head\n",
    "\n",
    "    def setNodes(self, head):\n",
    "        p_head = head\n",
    "        while p_head:\n",
    "            p_next = p_head.next\n",
    "            if p_head.random:\n",
    "                p_next.random = p_head.random.next\n",
    "            p_head = p_next.next\n",
    "        return head\n",
    "\n",
    "    def reconNodes(self, head):\n",
    "        new_head = head.next if head else None\n",
    "        p_new_head = new_head\n",
    "        while head:\n",
    "            head.next = None\n",
    "            head = p_new_head.next\n",
    "            if head:\n",
    "                p_new_head.next = head.next\n",
    "                p_new_head = p_new_head.next\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return\n",
    "        res = {}\n",
    "        node = head\n",
    "        while node is not None:\n",
    "            if node not in res:\n",
    "                res[node] = Node(node.val)\n",
    "            if node.next is not None:\n",
    "                if node.next not in res:\n",
    "                    res[node.next] = Node(node.next.val)\n",
    "                res[node].next = res[node.next]\n",
    "            if node.random is not None:\n",
    "                if node.random not in res:\n",
    "                    res[node.random] = Node(node.random.val)\n",
    "                res[node].random = res[node.random]\n",
    "            node = node.next\n",
    "        return res[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return\n",
    "        dummy = head\n",
    "        while head:\n",
    "            second = head.next\n",
    "            head.next = ListNode(head.val)\n",
    "            head.next.next = second\n",
    "            head = second\n",
    "        head = dummy\n",
    "        \n",
    "        while head:\n",
    "            second = head.next\n",
    "            if not head.random:\n",
    "                second.random = head.random\n",
    "            else:\n",
    "                second.random = head.random.next\n",
    "            head = head.next.next\n",
    "            \n",
    "        head = dummy\n",
    "        root = Node(1, None, None)\n",
    "        res = root\n",
    "        while head:\n",
    "            root.next = head.next\n",
    "            head = head.next.next\n",
    "            #print(root.next.val, root.next.random)\n",
    "            root = root.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        p = head\n",
    "        while p:\n",
    "            n_p = Node(p.val)\n",
    "            n_p.next = p.next\n",
    "            p.next = n_p\n",
    "            p = p.next.next\n",
    "        p = head\n",
    "        while p:\n",
    "            old_bkp = p.next.next\n",
    "            p.next.next = old_bkp.next if old_bkp else None\n",
    "            p.next.random = p.random.next if p.random else None \n",
    "            p = old_bkp\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None: return None\n",
    "        dummy = head\n",
    "        while dummy:  # 创建新结点，链接在原始结点后面\n",
    "            node = Node(dummy.val)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "            dummy = node.next\n",
    "        dummy = head\n",
    "        while dummy:  # 复制random信息\n",
    "            dummy.next.random = dummy.random.next if dummy.random else None\n",
    "            dummy = dummy.next.next\n",
    "\n",
    "        dummy = head.next\n",
    "        while dummy:  # 将复制的结点链接到新链表中\n",
    "            dummy.next = dummy.next.next if dummy.next else None\n",
    "            dummy = dummy.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited={}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        head_old=head\n",
    "        self.visited[head]=self.isCopied(head)\n",
    "        while head_old:\n",
    "            \n",
    "            self.visited[head_old].next=self.isCopied(head_old.next)\n",
    "            self.visited[head_old].random=self.isCopied(head_old.random)\n",
    "            head_old=head_old.next\n",
    "\n",
    "        return self.visited[head]  \n",
    "\n",
    "    def isCopied(self,node):\n",
    "        if not node:\n",
    "            return None\n",
    "        if node not in self.visited:\n",
    "            new_node=Node(node.val,None,None)\n",
    "            self.visited[node]=new_node\n",
    "        return self.visited[node] \n",
    "\n",
    "    \n",
    "        \n",
    "       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        cur = head\n",
    "        old2new = {}\n",
    "        if not head:\n",
    "            return None\n",
    "        while cur:\n",
    "            if cur not in old2new:\n",
    "                old2new[cur] = Node(cur.val)\n",
    "            if cur.next:\n",
    "                if cur.next not in old2new:\n",
    "                    old2new[cur.next] = Node(cur.next.val)\n",
    "                old2new[cur].next = old2new[cur.next]\n",
    "            if cur.random:\n",
    "                if cur.random not in old2new:\n",
    "                    old2new[cur.random] = Node(cur.random.val)\n",
    "                old2new[cur].random = old2new[cur.random]\n",
    "            cur = cur.next\n",
    "        return old2new[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        seen = {}\n",
    "        curr = head\n",
    "        while curr:\n",
    "            node_random = curr.random\n",
    "\n",
    "            new_node = seen.setdefault(curr, Node(curr.val))\n",
    "            if curr.next:\n",
    "                new_next = seen.setdefault(curr.next, Node(curr.next.val))\n",
    "                new_node.next = new_next\n",
    "            if curr.random:\n",
    "                new_random = seen.setdefault(node_random, Node(node_random.val))\n",
    "                new_node.random = new_random\n",
    "            curr = curr.next\n",
    "        return seen[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:        \n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        cur_node = head\n",
    "        head_new = None\n",
    "        last_node_new = None\n",
    "        node_list = []\n",
    "        node_list_new = []\n",
    "        while cur_node:\n",
    "            node_list.append(cur_node)\n",
    "            cur_node_new = Node(cur_node.val, None, None)\n",
    "            node_list_new.append(cur_node_new)\n",
    "\n",
    "            if last_node_new:\n",
    "                last_node_new.next = cur_node_new\n",
    "            else:\n",
    "                head_new = cur_node_new\n",
    "            last_node_new = cur_node_new\n",
    "            cur_node = cur_node.next\n",
    "            \n",
    "        for nix, cur_node in enumerate(node_list):\n",
    "            cur_node_rand = cur_node.random\n",
    "            if cur_node_rand:                \n",
    "                node_list_new[nix].random = node_list_new[node_list.index(cur_node_rand)]\n",
    "                \n",
    "        \n",
    "        return head_new\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = {}\n",
    "\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return head\n",
    "\n",
    "        if head in self.visited:\n",
    "            return self.visited[head]\n",
    "        \n",
    "        node = Node(head.val, None, None)\n",
    "        self.visited[head] = node\n",
    "        node.next = self.copyRandomList(head.next)\n",
    "        node.random = self.copyRandomList(head.random)\n",
    "    \n",
    "        return node\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.visitedHash = {}\n",
    "\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        if head in self.visitedHash:\n",
    "            return self.visitedHash[head]\n",
    "\n",
    "        node = Node(head.val, None, None)\n",
    "        \n",
    "        self.visitedHash[head] = node\n",
    "\n",
    "        node.next = self.copyRandomList(head.next)\n",
    "        node.random = self.copyRandomList(head.random)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        seen = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node in seen:\n",
    "                return seen[node]\n",
    "            curr = seen[node] = Node(node.val)\n",
    "            curr.next = dfs(node.next)\n",
    "            curr.random = dfs(node.random)\n",
    "            return curr\n",
    "\n",
    "        return dfs(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        node1 = head\n",
    "\n",
    "        while node1:\n",
    "            val = node1.val\n",
    "            new_node = Node(val,None,None)\n",
    "            new_node.random = node1.random\n",
    "            node1.random = new_node\n",
    "            node1 = node1.next\n",
    "\n",
    "        res = head.random\n",
    "\n",
    "        while head:\n",
    "            # if head.random.next:\n",
    "            if head.next:\n",
    "                head.random.next = head.next.random\n",
    "            else:\n",
    "                head.random.next = None\n",
    "            if head.random.random:\n",
    "                head.random.random = head.random.random.random\n",
    "            head = head.next\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head: return None\n",
    "\n",
    "        p = head\n",
    "        while p:\n",
    "            new_node = Node(p.val, None, None)\n",
    "            new_node.next = p.next\n",
    "            p.next = new_node\n",
    "            p = new_node.next\n",
    "        \n",
    "        p = head\n",
    "        while p:\n",
    "            if p.random:\n",
    "                p.next.random = p.random.next\n",
    "            p = p.next.next\n",
    "        \n",
    "        p = head\n",
    "        dummy = Node(-1, None, None)\n",
    "        cur = dummy\n",
    "        while p:\n",
    "            cur.next = p.next\n",
    "            cur = cur.next\n",
    "            p.next = cur.next\n",
    "            p = p.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        p = head\n",
    "        while p:\n",
    "            q = Node(p.val)\n",
    "            q.next = p.next\n",
    "            p.next = q\n",
    "            p = p.next.next\n",
    "\n",
    "        p = head\n",
    "        while p:\n",
    "             if p.random:\n",
    "                 p.next.random = p.random.next\n",
    "             p = p.next.next\n",
    "\n",
    "        ret = Node(0)\n",
    "        pre = ret\n",
    "        p = head\n",
    "        while p:\n",
    "            pre.next = p.next\n",
    "            pre = pre.next\n",
    "            p.next = pre.next\n",
    "            p = p.next\n",
    "\n",
    "        return ret.next    \n",
    "                     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if head==None:\n",
    "            return None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = Node(cur.val)\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = cur.next.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random = cur.random.next\n",
    "            cur = cur.next.next\n",
    "        cur = head\n",
    "        new_head = head.next\n",
    "        while cur.next:\n",
    "            tmp = cur.next\n",
    "            cur.next = tmp.next\n",
    "            cur = tmp\n",
    "        return new_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        mydict = {}\n",
    "        def recursion(node):\n",
    "            if not node:\n",
    "                return None \n",
    "            if node in mydict:\n",
    "                return mydict.get(node)\n",
    "\n",
    "            root = Node(node.val)\n",
    "            mydict[node] = root\n",
    "            root.next = recursion(node.next)   ###\n",
    "            root.random = recursion(node.random)  #######\n",
    "            return root\n",
    "        \n",
    "        return recursion(head)\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution(object):\n",
    "    def copyRandomList(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        p = head\n",
    "        # 第一步，在每个原节点后面创建一个新节点\n",
    "        # 1->1'->2->2'->3->3'\n",
    "        while p:\n",
    "            new_node = Node(p.val,None,None)\n",
    "            new_node.next = p.next\n",
    "            p.next = new_node\n",
    "            p = new_node.next\n",
    "        p = head\n",
    "        # 第二步，设置新节点的随机节点\n",
    "        while p:\n",
    "            if p.random:\n",
    "                p.next.random = p.random.next\n",
    "            p = p.next.next\n",
    "        # 第三步，将两个链表分离\n",
    "        p = head\n",
    "        dummy = Node(-1,None,None)\n",
    "        cur = dummy\n",
    "        while p:\n",
    "            cur.next = p.next\n",
    "            cur = cur.next\n",
    "            p.next = cur.next\n",
    "            p = p.next\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return None\n",
    "        map = dict()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            map[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            map[cur].next = map.get(cur.next)\n",
    "            map[cur].random = map.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return map[head]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "# Definition for a Node.\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        node_map = {}\n",
    "        p = q = Node(head.val)\n",
    "        node_map[head] = q\n",
    "        while head:\n",
    "            if head.next:\n",
    "                if head.next in node_map:\n",
    "                    q.next = node_map[head.next]\n",
    "                else:\n",
    "                    q.next = Node(head.next.val)\n",
    "                    node_map[head.next] = q.next\n",
    "            if head.random:\n",
    "                if head.random in node_map:\n",
    "                    q.random = node_map[head.random]\n",
    "                else:\n",
    "                    q.random = Node(head.random.val)\n",
    "                    node_map[head.random] = q.random\n",
    "            head = head.next\n",
    "            q = q.next\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:return \n",
    "        #构建字典\n",
    "        dic = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            dic[cur] = Node(cur.val) #原节点：新节点，只复制了节点没有复制指向\n",
    "            cur = cur.next\n",
    "        #复制random指向\n",
    "        cur = head\n",
    "        while cur:\n",
    "            dic[cur].next =dic.get(cur.next) #复制next指向,注意dic[cur]是值，在这里是新节点，也就是新节点的next从原节点cur去找\n",
    "            dic[cur].random = dic.get(cur.random) #复制random指向\n",
    "            cur = cur.next\n",
    "        return dic[head] #最后返回新节点的head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def copyNode(node, res):\n",
    "            if not node: return \n",
    "            if node in res: return res[node]\n",
    "\n",
    "            copy = Node(node.val, None, None)\n",
    "            res[node] = copy\n",
    "            copy.next = copyNode(node.next, res)\n",
    "            copy.random = copyNode(node.random, res)\n",
    "            return copy \n",
    "        return copyNode(head, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        hash_map = {}\n",
    "        def new_link(node:'Node') ->'Node':\n",
    "            if not node:\n",
    "                return None\n",
    "            if node in hash_map:\n",
    "                return hash_map[node]\n",
    "            hash_map[node] = Node(node.val)\n",
    "            hash_map.get(node).next = new_link(node.next)\n",
    "            hash_map.get(node).random = new_link(node.random)\n",
    "            return hash_map.get(node)\n",
    "        return new_link(head)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
